/**
 * @author ghp
 * @title
 */
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head.next == null) {
            // 链表只有一个节点，直接返回，防止后面出现NPE
            return true;
        }
        ListNode fast = head, slow = head, pre = null;
        // 定位中间节点，同时反转链表的前半段
        while (fast != null && fast.next != null) {
            // fast多走一步
            fast = fast.next.next;
            // 反转前半段链表
            ListNode next = slow.next;
            slow.next = pre;
            pre = slow;
            slow = next;
        }
        if (fast != null) {
            // 当前链表具有偶数个节点，还需要将slow往后移动一位
            slow = slow.next;
        }
        // 逐个比较 反转后的前半段链表 和 未反转的后半段链表 的节点的val是否相等
        while (pre != null && slow != null) {
            if (pre.val != slow.val) {
                // 有一个节点的val不相等，说明当前链表不是回文链表
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        // 前后两截链表的val都相等，则说明当前链表是回文链表
        return true;
    }
}
